#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct FreeArea
{               // 空闲区结构体
    int num;    // 分区号
    int start;  // 起始地址
    int length; // 长度
};
bool isLeagle(int start, int end);
void recycleMemory(vector<FreeArea> &areas, int start, int end);
void print(vector<FreeArea> &free_areas);
void mergeFreeAreas(vector<FreeArea> &areas);

const int MEMORY_SIZE = 128; // 内存大小为128K
int main()
{

    // 初始化空闲分区表
    vector<FreeArea> free_areas = {
        {1, 0, 127}};

    int choice;
    do
    {
        cout << "请选择操作:1.分配内存 2.回收内存 3.查看空闲内存分布 4.退出\n";
        cin >> choice;

        if (choice == 1)
        { // 分配内存
            int size;
            cout << "请输入需要分配的内存大小：";
            cin >> size;

            bool allocated = false; // 标记是否已经分配成功
            for (int i = 0; i < free_areas.size(); i++)
            {
                if (free_areas[i].length >= size)
                {                                           // 如果该空闲分区满足分配要求
                    int alloc_start = free_areas[i].start;  // 记录分配起始地址
                    int alloc_end = alloc_start + size - 1; // 计算分配结束地址
                    free_areas[i].start = alloc_end + 1;    // 更新空闲分区起始地址
                    free_areas[i].length -= size;           // 更新空闲分区长度

                    cout << "分配成功，起始地址为" << alloc_start << "，结束地址为" << alloc_end << endl;

                    allocated = true;
                    break;
                }
            }

            if (!allocated)
            { // 如果没有空闲分区满足分配要求
                cout << "内存不足，无法分配\n";
            }
        }
        else if (choice == 2)
        { // 回收内存
            int start, end;
            cout << "请输入需要回收的内存起始地址和结束地址：";
            cin >> start >> end;
            while (!isLeagle(start, end))
            {
                cout << "输入不合法，请重新输入" << endl;
                cin >> start >> end;
                continue;
            }
            recycleMemory(free_areas, start, end);
            // mergeFreeAreas(free_areas);

            cout << "内存释放成功\n";
            cout << "目前内存布局情况" << endl;
            print(free_areas);
        }
        else if (choice == 3)
        {
            print(free_areas);
        }
    } while (choice != 4);

    return 0;
}

void print(vector<FreeArea> &free_areas)
{
    cout << "区块号\t起始地址\t大小" << endl;
    for (int i = 0; i < free_areas.size(); i++)
    {
        cout << free_areas[i].num << '\t' << free_areas[i].start << "\t\t" << free_areas[i].length << endl;
    }
}

bool isLeagle(int start, int end)
{
    if (start > end || start < 0 || end > MEMORY_SIZE)
        return false;
    return true;
}

void recycleMemory(vector<FreeArea> &areas, int start, int end)
{
    cout << "end:::" << end << endl;
    vector<int> toBeDeleted;
    int new_begin = start + 1, new_end = end - 1;
    for (int i = 0; i < areas.size(); i++)
    {
        cout << "end:::" << end << endl;

        if (start > areas[i].start && end <= areas[i].start + areas[i].length)
        {
            cout << "该区域为空闲内存区，无需回收" << endl;
            return;
        }
        if (
            (start > areas[i].start && end > areas[i].start + areas[i].length) ||
            (start < areas[i].start && end <= areas[i].start + areas[i].length) ||
            (start < areas[i].start && end >= areas[i].start + areas[i].length))
        {
            toBeDeleted.push_back(i);
            if (start > areas[i].start)
                new_begin = areas[i].start;
            if (end <= areas[i].start + areas[i].length)
                new_end = areas[i].start + areas[i].length;
        }
        // if (areas[i].start >= start && areas[i].start + areas[i].length <= end)
        // {
        //     toBeDeleted.push_back(i);
        // }
    }
    cout << "end:::" << end << endl;

    start = start > new_begin ? new_begin : start;
    end = end < new_end ? new_end : end;
    if (toBeDeleted.size() > 1)
    {
        FreeArea mergedArea = {toBeDeleted[0], start, end - start + 1};
        areas.erase(areas.begin() + toBeDeleted.front(), areas.begin() + toBeDeleted.back() + 1);
        areas.push_back(mergedArea);
        return;
    }
    FreeArea a = {areas.size() + 1, start, end - start + 1};
    areas.push_back(a);
}